Sau khi Thốc Phát Ô Cô lập nước Nam Lương vào năm 397 bằng việc đoạn tuyệt với Hậu Lương, Thốc Phát Nục Đàn ngay lập tức đã được giao một vai trò quan trọng trong cả hai công việc quân sự và quản trị của đất nước. Năm 398, Thốc Phát Ô Cô cử ông đến giúp đỡ những đội quân nổi loạn của Dương Quỹ (楊軌) và Quách Nôn (郭黁) tại Hậu Lương. Vào mùa xuân năm 399, sau khi Thốc Phát Ô Cô dời đô từ Liêm Xuyên (廉川, nay thuộc Hải Đông, Thanh Hải) đến Lạc Đô (樂都, cũng thuộc Hải Đông ngày nay) trong một đợt tái tổ chức nhằm tăng cường sức mạnh quân sự, Thốc Phát Nục Đàn được giao trấn giữ thành Tây Bình (西平, nay thuộc Tây Ninh, Thanh Hải), và thời điểm này, ông được sử sách nói đến cùng với tước hiệu Quảng Vũ công, tức tước hiệu của Thốc Phát Ô Cô trước đó. Vào mùa hè năm 399, Thốc Phát Ô Cô triệu hồi ông vầ Lạc Đô để đứng đầu chính quyền, còn Thốc Phát Lợi Lộc Cô thay ông trấn thủ Tây Bình.

Đến năm 399, Thốc Phát Ô Cô bị một chấn thương nghiêm trọng khi cưỡi ngựa lúc đang say rượu, và trong những lời trăn chối cuối cùng, ông đã yêu cầu nên tìm một ai đó lớn tuổi để kế vị, các quý tộc Nam Lương đã ủng hộ Thốc Phát Lợi Lộc Cô lên kế vị. Thốc Phát Lợi Lộc Cô giao phó tất cả các vấn đề triều chính quan trọng cho ông và chỉ định ông là người kế vị.

Năm 400, khi hoàng đế Lã Toản của Hậu Lương tấn công nước Bắc Lương, Thốc Phát Nục Đàn đã tấn công bất ngờ vào kinh thành Cô Tang (姑臧, nay thuộc Vũ Uy, Cam Túc) của Hậu Lương. Ông đã vào được trong thành và tổ chức một bữa tiệc, buộc 8.000 hộ phải tái định cư đến Nam Lương cùng với ông.

Cũng trong năm 400, khi phải hứng chịu các thất bại dưới tay Hậu Tần, vua Khất Phục Càn Quy của Tây Tần đã đến chỗ Thốc Phát Lợi Lộc Cô đầu hàng, Thốc Phát Lợi Lộc Cô đã cử Thốc Phát Nục Đàn đi nghênh đón ông ta. Có lẽ vào thời điểm này, Thốc Phát Nục Đàn đã gả một con gái cho con trai của Khất Phục Càn Quy là Khất Phục Sí Bàn, song điều này không thật rõ ràng. Đến cuối năm đó, Khất Phục Càn Quy lại chạy trốn đến Hậu Tần đầu hàng, còn Khất Phục Càn Quy muốn đến chỗ phụ thân song bị bắt lại, theo lời đề nghị của Thốc Phát Nục Đàn nên Thốc Phát Lợi Lộc Cô đã không cho giết Khất Phục Sí Bàn.

Cũng trong khoảng thời gian này, tướng Khương Kỉ (姜紀) của Hậu Lương đã đến Nam Lương đầu hàng. Thốc Phát Nục Đàn ấn tượng trước tài năng của Khương Kỉ nên đã kết bằng hữu với người này và giành nhiều thời gian bên cạnh ông ta, mặc dù vậy, Thốc Phát Lợi Lộc Cô không tin tưởng Khương Kỉ. Tuy nhiên, Khương Kỉ đã sớm quay sang chống lại Nam Lương và chạy trốn đến Hậu Tần, bày cho hoàng đế Diêu Hưng của Hậu Tần các sách lược để chinh phục Hậu Lương và chống lại Nam Lương.

Khoảng tết năm 402, tướng nổi loạn Tiêu Lãng (焦朗) tại Hậu Lương đã tìm kiếm sự trợ giúp của Nam Lương, và Thốc Phát Lợi Lộc Cô đã cử Thốc Phát Nục Đàn đến giúp ông ta, song khi Thốc Phát Nục Đàn đến, Tiêu Lãng đã không tiếp đón ông. Thốc Phát Nục Đàn ban đầu tức giận và muốn quay sang tấn công Tiêu Lãng, song nghe theo đề xuất của Thốc Phát Câu Diên (禿髮俱延), ông đã hòa giải với Tiêu Lãng và hợp sức tiến đánh Cô Tang. Mặc dù liên quân đã không chiếm được thành vào thời điểm đó song đã giáng cho tướng Lã Siêu (呂超) của Hậu Lương một thất bại lớn. Tuy nhiên, cũng trong năm đó, khi vua Thư Cừ Mông Tốn của Bắc Lương tiến đánh Hậu Lương, Thốc Phát Nục Đàn lại đến trợ giúp cho Hậu Lương. Thốc Phát Nục Đàn ngay sau đó cũng đã bắt Tiêu Lãng và giải người này đến chỗ Thốc Phát Lợi Lộc Cô.

Đến năm 402, Thốc Phát Lợi Lộc Cô lâm bệnh và qua đời, ông đã để lại di chiếu truyền ngai vàng lại cho Thốc Phát Nục Đàn. Thốc Phát Nục Đàn chấp thuận và cho dời đô từ Tây Bình về Lạc Đô.